import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 981. 基于时间的键值存储
 * https://leetcode-cn.com/problems/time-based-key-value-store/
 */
public class Solutions_981 {
    public static void main(String[] args) {
//        TimeMap obj = new TimeMap();
//        obj.set("foo", "bar", 1);
//        String res1 = obj.get("foo", 1);  // output: bar
//        String res2 = obj.get("foo", 3);  // output: bar
//        obj.set("foo", "bar2", 4);
//        String res3 = obj.get("foo", 4);  // output: bar2
//        String res4 = obj.get("foo", 5);  // output: bar2

        TimeMap obj = new TimeMap();
        obj.set("love", "high", 10);
        obj.set("love", "low", 20);
        String res1 = obj.get("love", 5);  // output: ""
        String res2 = obj.get("love", 10);  // output: "high"
        String res3 = obj.get("love", 15);  // output: "high"
        String res4 = obj.get("love", 20);  // output: "low"
        String res5 = obj.get("love", 25);  // output: "low"
        System.out.println("");
    }
}

class MyData {
    String val;
    int time;

    MyData(String value, int timestamp) {
        this.val = value;
        this.time = timestamp;
    }
}

class TimeMap {
    // key：键，value：键对应的不同时间戳时的值
    Map<String, List<MyData>> map = null;

    /** Initialize your data structure here. */
    public TimeMap() {
        map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(new MyData(value, timestamp));
    }

    // 二分查找，得到列表中比 timestamp 小的最大时间戳
    // 所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的，所以 list 一定是针对 timestamp 的有序列表
    public String get(String key, int timestamp) {
        List<MyData> list = map.getOrDefault(key, null);
        if (list != null) {
            // key 的最小时间戳都大于 timestamp，那么无法找到小于等于 timestamp 的时间戳
            if (list.get(0).time > timestamp) {
                return "";
            }
            int left = 0;
            int right = list.size() - 1;
            while (left <= right) {
                // 找到中间点
                int mid = left + (right - left) / 2;
                // 中间点上的时间戳
                int midTime = list.get(mid).time;

                if (midTime == timestamp) {
                    return list.get(mid).val;
                } else if (midTime < timestamp) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            // 取最终 right 索引上的值
            return list.get(right).val;
        }
        return "";
    }
}
